<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <!-- link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css" -->

  <link rel="stylesheet" href="http://acm.math.spbu.ru/~sk1/colorer1/xcode.css">
  <script src="http://acm.math.spbu.ru/~sk1/colorer1/highlight.pack.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>

  <!--script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script -->
</head>

<body>

<pre><code>
/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 */

#include &lt;cstdio&gt;
#include &lt;cassert&gt;
#include &lt;algorithm&gt;

using namespace std;

#define forn(i, n) for (int i = 0; i &lt; (int)(n); i++)

const int maxt = (int)1e7;

struct tree
{
  int l, r;
};

tree t[maxt];
int tpos = 0;

inline int NewT( int l, int r )
{
  assert(tpos &lt; maxt);
  t[tpos].l = l;
  t[tpos].r = r;
  return tpos++;
}

struct PArray // Persistent Array
{
  int n, root;

  int Build( int n, int *a )
  {
    if (n == 1)
      return NewT(*a, *a);
    int m = n &gt;&gt; 1;
    return NewT(Build(m, a), Build(n - m, a + m));
  }
  
  PArray( int _n, int *a ) : n(_n), root(Build(n, a)) { }
  PArray( int _n, int _root ) : n(_n), root(_root) { }
  PArray() { }

  int Get( int v, int n, int k )
  {
    if (n == 1)
      return t[v].l;
    int m = n &gt;&gt; 1;
    return k &lt; m ? Get(t[v].l, m, k) : Get(t[v].r, n - m, k - m);
  }

  int operator [] ( int i )
  {
    return Get(root, n, i);
  }

  int Change( int v, int n, int i, int x )
  {
    if (i &lt; 0 || i &gt;= n)
      return v;
    if (n == 1)
      return NewT(x, x);
    int m = n / 2;
    return NewT(Change(t[v].l, m, i, x), Change(t[v].r, n - m, i - m, x));
  }

  PArray Change( int i, int x )
  {
    return PArray(n, Change(root, n, i, x));
  }
};

struct DSU // Disjoint-Set-Union
{
  PArray p, s;

  DSU( int n, int *p0, int *s0 ) : p(n, p0), s(n, s0) { }
  DSU( PArray _p, PArray _s ) : p(_p), s(_s) { }
  DSU() { }

  int Get( int v )
  {
    int tmp;
    while (v != (tmp = p[v]))
      v = tmp;
    return v;
  }

  DSU Join( int a, int b )
  {
    a = Get(a), b = Get(b);
    if (a != b)
    {
      if (s[a] &gt; s[b])
        swap(a, b);
      return DSU(p.Change(a, b), s.Change(b, s[a] + s[b]));
    }
    return *this;
  }
};

const int maxn = (int)1e5;
const int maxk = (int)1e5;

int n, k, p[maxn], s[maxn];
DSU rev[maxk];

int main()
{
  assert(scanf("%d%d", &n, &k) == 2);
  assert(1 &lt;= n && n &lt;= maxn);
  assert(0 &lt;= k && k &lt;= maxk);
  forn(i, n)
    p[i] = i, s[i] = 1;
  rev[0] = DSU(n, p, s);

  forn(i, k)
  {
    char com;
    int a, b, ind;
    assert(scanf(" %c%d%d%d", &com, &ind, &a, &b) == 4), a--, b--;
    assert(com == '+' || com == '?');
    assert(0 &lt;= ind && ind &lt;= i);
    assert(0 &lt;= a && a &lt; n && 0 &lt;= b && b &lt; n);
    if (com == '+')
      rev[i + 1] = rev[ind].Join(a, b);
    else
      puts(rev[ind].Get(a) == rev[ind].Get(b) ? "YES" : "NO");
  }
  return 0;
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
